#include <stdlib.h>
#include <stdio.h>
#include "minqueue.h"

MinQueue::MinQueue()
{
    _anData=NULL;
    _nLength=0;
    _nMinExtraction=Nill;
    _nKnotsLength=0;
}

MinQueue::MinQueue(const int* data, int n)
{
    initWithData(data, n);
}

void MinQueue::printContents()
{
    fprintf(stderr, "Contents of the queue:\n");
    for(int i=0; i<_nLength; i++)
        fprintf(stderr, "%d Contains: %d\n", i, _anData[i]);
}

void MinQueue::initWithData(const int* data, int n)
{
    _nLength=n;
    _anData = (int*)malloc(sizeof(int)*n);
    for(int i=0; i<n; i++)
	_anData[i]=data[i];
// our data has to be sorted after it was inserted:
    sort();
}

void MinQueue::setKnots(Knots* kn, int count){ _Knots=kn;_nKnotsLength=count;}

void MinQueue::setMinExtr(int a){_nMinExtraction=a;}

int MinQueue::extract_min()
{
    int min=Infinity;
    int nFound=Nill;
    bool bWasDiscovered=false;

    for(int i=0; i<_nLength; i++)
	// we've found the next one knot, try it... 
	if(min>abs(_nMinExtraction-_anData[i])){
	    // find out, if the knot has a parent with discovered links:
	    for(int k=0; k<_nKnotsLength; k++)
                // found the knot, which connections have to be checked:
                if(_Knots[k]._nKnot==_anData[i])
		{
		    // if we couldn't find a record in our _anData
		    // this means this record was discovered before and we
		    // can use this one in our calculations:
		    for(int m=0; m<_Knots[k]._nCountWhere; m++){
			bWasDiscovered=false;
			for(int f=0;f<_nLength; f++){
                            if(_Knots[k]._aWhereToGo[m].knot==i)continue;
			    // we've found a used element, 
			    if(_Knots[k]._aWhereToGo[m].knot==_anData[f]){
				bWasDiscovered=true;
				break;
			    }
			}
			if(!bWasDiscovered)break;
		    }
		}
	    if(!bWasDiscovered){
		min=abs(_nMinExtraction-_anData[i]);
		nFound=i;
	    }
        }
	else{
	    // if we've found a minimul index:
	    if(min < Infinity/*&& nFound!=Nill*/)
		break;
	}

        // push out the found element:
    int out=_anData[nFound];
    for(int i=nFound; i<_nLength-1; i++)
	_anData[i]=_anData[i+1];
    _nLength--;

    return out;
}

bool MinQueue::areThereMoreElements()
{
    return (_nLength>0);
}

MinQueue::~MinQueue()
{
    if(_anData != NULL)
	free(_anData);
}

// TODO: insert another method of sorting (this one is too slow)
void MinQueue::sort()
{
    int key=0;
    for(int j=1; j<_nLength; j++)
    {
	key=_anData[j];
	int i=j-1;
	while(i>=0 && _anData[i] > key)
	{
	    _anData[i+1]=_anData[i];
	    i--;
	}
	_anData[i+1]=key;
    }
}
